package 算法.NiuKe.JZ;

import java.util.ArrayList;
import java.util.List;

/**
 * @author:谢君臣
 * @Date:2021/4/1113:35
 * @version:1.0
 * @function: 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。
 * 并将P对1000000007取模的结果输出。 即输出P%1000000007
 */
public class JZ35 {
    public static void main(String[] args) {
        System.out.println(reversePairs(new int[]{1, 3, 2, 3, 1}));
    }

    public static int reversePairs(int[] nums) {
        int length = nums.length;
        if (length < 1) return 0;
        int[] copy = nums.clone();
        int[] temp = new int[nums.length];
        return reversePairs(copy, 0, length - 1, temp);
    }

    public static int reversePairs(int[] nums, int l, int r, int[] temp) {
        if (l == r)
            return 0;
        int mid = (r - l) / 2 + l;
        int left = reversePairs(nums, l, mid, temp);
        int right = reversePairs(nums, mid + 1, r, temp);
        int cross = calcul(nums, l, mid, r, temp);
        return left + right + cross;
    }

    /**
     * 计算跨区间的逆序对的个数 nums[l...mid]、nums[mid+1...r] 保证区间是有序的
     * @param nums
     * @param l    左边带归并的下标
     * @param mid
     * @param r
     * @param temp
     * @return
     */
    private static int calcul(int[] nums, int l, int mid, int r, int[] temp) {
        int count = 0;
        if (r - l >= 0) System.arraycopy(nums, l, temp, l, r-l+1);
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i==mid+1)
                nums[k] = temp[j++];
            else if (j==r+1)
                nums[k] = temp[i++];
            else if (temp[i] <= temp[j])
                nums[k] = temp[i++];
            else{
                nums[k] = temp[j++];
                count += mid-i+1;
            }
        }
        return count;
    }
    public static int sum = 0;
    public static int InversePairs(int[] array) {
        if (array.length == 0) {
            return 0;
        }
        List<Integer> list = new ArrayList<>();
        list.add(array[0]);
        for (int i = 1; i < array.length; i++) {
            list = addElement(list, array[i]);
        }
        return sum;
    }

    private static List<Integer> addElement(List<Integer> list, int target) {
        int i = 0;
        while (i < list.size() && list.get(i) <= target) i++;
        sum += list.size() - i;
        list.add(i, target);
        return list;
    }
}
